package com.facebook.app.server.clustering;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

import com.facebook.app.shared.clustering.Cluster;
import com.facebook.app.shared.clustering.Clusterable;

public class HierarchicalClusteringWithArrays implements
		ClusteringStrategy {

	private final int numberOfLoopsPerRequest;
	private final ClusterSimilarityStrategy similarityStrategy;

	private List<Clusterable> clusterElements;

	public HierarchicalClusteringWithArrays(ClusterSimilarityStrategy similarityStrategy, List<Clusterable> clusterElements) {
		
		this.similarityStrategy = similarityStrategy;

		if (clusterElements instanceof ArrayList) {
			this.clusterElements = clusterElements;
		} else {
			this.clusterElements = new ArrayList<Clusterable>(clusterElements);
		}

		// The number of loops per request should depend on
		// the number of elements in the Clusterable list.

		// for testing
		numberOfLoopsPerRequest = Integer.MAX_VALUE;
	}

	@Override
	public List<Clusterable> createClusters() {

		if (clusterElements.size() < 2) {
			return clusterElements;
		}

		double[][] similarityMatrix = new double[clusterElements.size() - 1][];

		// creating the similarityMatrix:
		for (int i = 0; i < similarityMatrix.length; i++) {
			similarityMatrix[i] = new double[clusterElements.size() - i - 1];

			for (int j = 0; j < similarityMatrix[i].length; j++) {
				similarityMatrix[i][j] = similarityStrategy.computeSimilarity(
						clusterElements.get(i), clusterElements.get(i + j + 1));
			}
		}

		double maxSimilarityScore;
		int indexOfHighestScoredPairFirstElement = 0;
		int indexOfHighestScoredPairSecondElement = 0;

		// After the loop has run through clusterElements.size() - 1 iterations,
		// there is only one element left.
		for (int k = 0; k < numberOfLoopsPerRequest
				&& k < clusterElements.size() - 1; k++) {
			maxSimilarityScore = Double.NEGATIVE_INFINITY;

			// chooses the Clusterable pair with the highest similarity
			for (int i = 0; i < similarityMatrix.length; i++) {
				if (similarityMatrix[i] != null) {
					for (int j = 0; j < similarityMatrix[i].length; j++) {
						if (similarityMatrix[i][j] > maxSimilarityScore) {
							maxSimilarityScore = similarityMatrix[i][j];
							indexOfHighestScoredPairFirstElement = i;
							indexOfHighestScoredPairSecondElement = i + j + 1;
						}
					}
				}
			}

			Clusterable newNode = new Cluster(
					clusterElements.get(indexOfHighestScoredPairFirstElement),
					clusterElements.get(indexOfHighestScoredPairSecondElement),
					maxSimilarityScore);

			// important: highestScoredPairFirstElementIndex is always lower
			// than highestScoredPairSecondElementIndex

			clusterElements.set(indexOfHighestScoredPairFirstElement, newNode);
			clusterElements.set(indexOfHighestScoredPairSecondElement, null);

			/*
			 * Now, the similarities between the second (removed) element and
			 * the remaining ones are "removed" (set to
			 * Double.NEGATIVE_INFINITY). The similarities between the new
			 * Cluster and the remaining elements are calculated and added.
			 */
			for (int i = 0; i < indexOfHighestScoredPairSecondElement; i++) {
				if (similarityMatrix[i] != null) {
					if (i < indexOfHighestScoredPairFirstElement) {
						similarityMatrix[i][indexOfHighestScoredPairFirstElement
								- i - 1] = similarityStrategy.computeSimilarity(newNode,
								clusterElements.get(i));
					}

					similarityMatrix[i][indexOfHighestScoredPairSecondElement
							- i - 1] = Double.NEGATIVE_INFINITY;
				}
			}

			for (int i = 0; i < similarityMatrix[indexOfHighestScoredPairFirstElement].length; i++) {
				if (similarityMatrix[indexOfHighestScoredPairFirstElement][i] > Double.NEGATIVE_INFINITY) {
					similarityMatrix[indexOfHighestScoredPairFirstElement][i] = similarityStrategy.computeSimilarity(
							newNode,
							clusterElements
									.get(indexOfHighestScoredPairFirstElement
											+ i + 1));
				}
			}

			// highestScoredPairSecondElementIndex is equal to
			// similarityMatrix.length
			// if the last Clusterable in the list was chosen to be
			// clustered.
			if (indexOfHighestScoredPairSecondElement < similarityMatrix.length) {
				similarityMatrix[indexOfHighestScoredPairSecondElement] = null;
			}
		}

		List<Clusterable> remainingClusterElements = new LinkedList<Clusterable>();

		for (Clusterable element : clusterElements) {
			if (element != null) {
				remainingClusterElements.add(element);
			}
		}

		return remainingClusterElements;
	}

}
